#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;

ListNode* partition(ListNode* pHead, int x) {
    // write code here
    // if(pHead==nullptr)
    //     return nullptr;
    ListNode *lesshead, *lesstail, *greaterhead, *greatertail;
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));

    greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* p = pHead;
    while (p) {
        if (p->val < x) {
            lesstail->next = p;
            lesstail = lesstail->next;
        }
        else {
            greatertail->next = p;
            greatertail = greatertail->next;
        }
        p = p->next;
    }

    greatertail->next = NULL;
    lesstail->next = greaterhead->next;
    ListNode* ptr = lesshead->next;

    free(lesshead);
    free(greaterhead);
    lesshead = greaterhead = NULL;

    return ptr;
}
int main()
{

	return 0;
}

